1. Field of the Invention
This invention relates to the general field of optical flow computation in images, and more specifically, to the field of visual motion sensing chips.
2. Description of the Related Art
The term "optical flow" generally refers to the motion of texture seen by an agent (such as an animal or a robot) as a result of relative motion between the agent and other objects in the environment. It is well known that animals, especially insects, use information from the optical flow for depth perception and to move about in an environment without colliding into obstacles. Robotics and machine vision researchers have borrowed from these ideas in biology to build machine vision systems that successfully use optical flow for depth perception and obstacle avoidance. These successes verify that optical flow can indeed be used for depth perception and obstacles avoidance in real systems.
In robotics and machine vision, optical flow is mathematically expressed as a vector field either in the two-dimensional visual field 105 or in an image focal plane created by a lens. In the subsequent discussion, no differentiation is made between these two variations.
The value of the optic flow vector 103 (FIG. 1) at a location in the visual field 105 (FIG. 1) refers to the velocity at which texture 107 (FIG. 1) is moving in that location of the visual field 105. To measure optical flow, typical machine vision systems grab sets of two-dimensional pixel array images using a camera, and use these sequential images to measure the optical flow field. In general, algorithms for computing optical flow from a set of images are computationally intensive, resulting in the need for a large amount of computing power for the computation of optical flow. This is because optical flow is a phenomena that has both spatial and temporal aspects, hence a large amount of data (two-dimensions of image and one dimension of time) needs to be processed. This is especially true if the image is sensed with a charge coupled device (CCD) or another pixel-structured type of image sensor. Almost all modem machine vision systems use such pixel-structured cameras. A discussion of the variety of algorithms used to measure optical flow is beyond the scope of this invention. However two of the more successful and popular approaches, the correlation method and the gradient method, are applicable to this sensor.
The correlation method of measuring optic flow will be qualitatively discussed by now referring to FIGS. 2a through 2c. FIGS. 2a and 2b show two successive frames or images of a video sequence. FIG. 2a shows the first frame 115, a location 117 in the first frame, and a block of texture 119 in the first frame. FIG. 2b shows the second frame 121, the search space 123 for a block that matches the first frame's block 119, and the best matching block 125. FIG. 2c shows a resulting optic flow vector 127. In the correlation method, to measure the optic flow at a location 117 in the visual field 105 generating the first frame 115, first a block of texture 119 is selected that contains the location 117. Next a search is conducted in the second frame 121 over a search space 123 for the block 125 that best matches the first image's block 119. A correlation function is typically used to measure how well two blocks 119 and 125 match, hence the name of the algorithm. A distance function between the two blocks 119 and 125 can also be used, where the best match is found by minimizing distance. The displacement between the first frame's block 119 and the second framers best matching block 125 is used to form the resulting optic flow vector 127, shown in FIG. 2c. This process is repeated over the entire image 115 to compute a complete optic flow field. To summarize. essentially this algorithm tracks texture and picture details such as points and edges, and uses the resulting displacements to measure optic flow. In more advanced versions of this algorithm, ideas from signal processing and estimation theory can be used to improve performance. For example, Kalman filters can be used to aid the tracking of features over multiple sequential images. A discussion of these techniques is beyond the scope of this invention but can be found in the general open literature.
This method of computing optical flow is intuitive. However it is brute force, and hence computationally intensive when performed on two-dimensional images. However the computational complexity is greatly reduced when performed on one-dimensional images. This is for two reasons: first, because block matching computations need to be performed with blocks of one-dimension rather than two: and second, the range of potential displacements to be searched covers one-dimension rather than two. It will be seen that the photoreceptor array of this invention provides a useful one-dimensional image.
The gradient method of measuring optic flow will now be discussed. The gradient method of computing optical flow assumes that the local shape of the image remains constant while it is moving. Then by comparing the spatial partial derivatives of the image intensity, which contains information on the shape of the image if plotted as a curve, with the temporal partial derivatives, which is how fast the intensity at a location is getting brighter or dimmer, knowledge about the image motion can be had. FIG. 2 is used to explain the gradient method on a one dimensional image. In FIG. 3, shown is a time varying image intensity curse I(x,t) 129, the velocity .nu. 131, the slope of the spatial intensity partial derivative I.sub.x (x,t) 133, and the temporal intensity partial derivative I.sub.t (x,t) 135 are shown. In the gradient method, just like the correlation method, it is assumed that the general shape of the image intensity I(x,t) 129 remains the same but translates at the constant velocity .nu. 131. This assumption is expressed by the mathematical equation EQU I(x,t+.DELTA.t)=I(x-.nu..DELTA.t,t).
The spatial intensity derivative I.sub.x (x,t) 133, formally given as ##EQU1##
expresses how fast the image intensity 129 changes when time is frozen and as the variable x moves in the positive X direction. The temporal intensity derivative I.sub.t (x,t) 135, formally given as ##EQU2##
expresses how fast the image intensity at a single location changes as a result of texture motion.
Given the above assumption that the shape of the image remains the same and just translates in time, the spatial partial derivative I.sub.x (x,t) 133 and temporal partial derivative I.sub.t (x,t) 135 follow the relationship EQU I.sub.t (x,t)=-.nu.I.sub.x (x,t).
Thus ##EQU3##
Therefore if both I.sub.x (x,t) 133 and I.sub.t (x,t) 135 are known, then the image motion .nu. 131 can be estimated.
The values I.sub.x (x,t) and I.sub.t (x,t) are easy to compute when using a one dimensional image. I.sub.x (x,t) can be approximated by ##EQU4##
where .DELTA.x is the distance between two nearby pixels on the image. Essentially two nearby locations of the image are looked at simultaneously and then their difference computed to approximate the spatial intensity derivative I.sub.x (x,t). Likewise I.sub.t (x,t) can be approximated by ##EQU5##
where .DELTA.t is the time interval between two samplings of an image location. Essentially the intensity at the image location is looked at twice at two different times, and the change in intensity used to compute the temporal intensity derivative I.sub.t (x,t). The two above methods of estimating the intensity derivatives 133 and 135 is derived straight from basic differential calculus.
In two dimensions the general approach is the same but computationally much more difficult to solve. To understand this difficulty, consider the following problem formulation. Let I(x,y,t) represent the image intensity at point (x,y) at time t. Let .nu..sub.x and .nu..sub.y respectively represent the x and y components of the texture velocity. The two spatial derivatives are I.sub.x (x,y,t) and I.sub.y (x,y,t) respectively for the x and y directions. I.sub.t (x,y,t) is how fast the image intensity is changing at one location as a result of texture motion. The spatial gradients and the temporal gradient follows the rule EQU I.sub.t (x,y,t)=-.nu..sub.x I.sub.x (x,y,t)-.nu..sub.y I.sub.y (x,y,t).
There is one equation for the two unknown velocity variables, hence it is impossible to determine the texture motion by looking at this one point. The way this problem is typically addressed in the current art is to first generate a set of equations by applying the above rule over a set of points in the image. Then a set of additional constraints is used to find solutions to these equations. An example of such a constraint is to assume that the texture motion in nearby locations is similar, thus causing an algorithm to favor solutions with such characteristics. Much work has been performed in this general technique, however the best algorithms are still computationally intensive.
Some researchers have taken the alternative approach of building application specific integrated circuits (ASICs) that use a combination of digital and analog circuitry to measure optical flow. The idea behind this approach is that specifically designed analog and digital circuits can perform the computations necessary to measure optical flow in a much more compact fashion than is possible with a general purpose Von-Neumann type computer. This is especially useful if the implemented algorithm is one that can be mapped onto an array of parallel processors. These efforts have resulted in single or multiple chip systems that measure optical flow. However the vast majority of these chips still use a two-dimensional pixel-structured representation of the image, which is not necessarily a good representation for optical flow computation. Furthermore in many of these cases the circuits implement hard-wired versions of conventional algorithms. Thus the speed increase comes only from implementing an algorithm in digital hardware rather than software. Speed increases that could be had by using algorithms that map elegantly into the hardware are ignored. Finally a significant problem with most of these chips is that they do not function well with low contrast images.
The present invention overcomes the problems of computational complexity by using specially shaped photoreceptor circuits to generate a one-dimensional image representation of the two-dimensional visual field region of interest. These photoreceptor circuits preserve information in one direction of the two dimensional visual field while eliminating information in the perpendicular direction. This transformation is performed entirely with optics and simple analog circuitry. Then optic flow is measured by giving the one-dimensional image to an optic flow algorithm. The required computing power is reduced because one-dimensional optic flow is significantly easier to compute than two-dimensional optic flow. However as a result of the photoreceptors having an orientation in the visual field, the one-dimensional optic flow measurement has meaning in the two dimensional visual field. As will be discussed, several of these sensors placed in the same area of the visual field and oriented in different directions can extract two dimensional optic flow information.